package or;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

public class T0464 {

    Map<Integer, Boolean> map = new HashMap<>();

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {

        if ((maxChoosableInteger+1)*maxChoosableInteger/2 <desiredTotal){
            return false;
        }
        return dfs(maxChoosableInteger, desiredTotal, 0, 0);

    }

    public boolean dfs(int maxChoosableInteger, int desiredTotal, int sumSelected, int selected) {

        if (!map.containsKey(selected)) {
            boolean boo = false;
            for (int i = 0; i < maxChoosableInteger; i++) {
                if (((selected >> i) & 1) == 0) {
                    if (sumSelected + i + 1 >= desiredTotal) {
                        boo = true;
                        break;
                    }
                    if (!dfs(maxChoosableInteger, desiredTotal, sumSelected + i + 1, selected | (1 << i))) {
                        boo = true;
                        break;
                    }

                }

            }
            map.put(selected,boo);


        }
        return map.get(selected);


    }

    @Test
    public void test() {

        System.out.println(canIWin(10,11));

    }


}
